package LeetCode.Leet700_799.Leet790_799.Leet797;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/9/17 12:45
 * @Description TODO: 方法一   dfs（深度优先搜索，递归回溯）    2ms 92.67%
 *                   有向无环图，不会出现死循环
 */
class Solution_1 {
    List<List<Integer>> result;  // 结果
    List<Integer> path;  // 其中一条路径
    int[][] graph;  // 存储图
    int n;  // 节点个数，也为终点
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // dfs
        result = new ArrayList<>();
        path = new ArrayList<>();
        path.add(0);
        this.graph = graph;
        n = graph.length;
        doAllPathsSourceTarget(0);
        return result;
    }

    public void doAllPathsSourceTarget(int start){
        // 到达终点，记录路径
        if(start == n - 1){
            result.add(new ArrayList<>(path));
            return;
        }
        // 递归回溯
        for(int i = 0;i < graph[start].length;i++){
            // 将下一个节点加入到路径中
            path.add(graph[start][i]);
            doAllPathsSourceTarget(graph[start][i]);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}
